#-------------------------------------------
#===========================================

class Node(object):
	def __init__(self, value):
		self.left = NULL
		self.right = NULL
		self.value = value

	def getMinLength(self):
		if self.left == NULL or self.right == NULL:
			return 1
		elif self.left != NULL and self.right == NULL:
			return 1 + self.left.getMinLength()
		elif self.right != NULL and self.left == NULL:
			return 1 + self.right.getMinLength()
		else:
			return min(1 + self.right.getMinLength(), 1 + self.left.getMinLength())

	def getMaxLength(self):
		if self.left == NULL and self.right == NULL:
			return 1
		elif self.left != NULL:
			return 1 + self.left.getMaxLength()
		elif self.right != NULL:
			return 1 + self.right.getMaxLength()
		else:
			return max(1 + self.right.getMaxLength(), 1 + self.left.getMaxLength())

	def setLeft(self, node):
		self.left = node

	def setRight(self, node):
		self.right = node

	def copy(self):
		copy = Node(self.value)
		copy.right = self.right.copy()
		copy.left = self.left.copy()
		return copy

class NodeNull(Node):
	def __init__(self):
		pass

	def __eq__(self, other):
		if type(other) == NodeNull:
			return True
		return False

	def copy(self):
		return NodeNull()

NULL = NodeNull()

#-------------------------------------------
#===========================================
class Tree(object):
	def __init__(self, root):
		self.root = root

	def getMaxLength(self):
		if self.root == NULL:
			return 0
		else:
			return self.root.getMaxLength()

	def getMinLength(self):
		if self.root == NULL:
			return 0
		else:
			return self.root.getMinLength()

	def copy(self):
		copy = Tree(self.root.copy())
		return copy

#-------------------------------------------
#===========================================
if __name__ == '__main__':
	node1 = Node(1)
	node2 = Node(2)
	node3 = Node(3)
	node4 = Node(4)
	node5 = Node(5)
	node6 = Node(6)
	node7 = Node(7)
	node1.setLeft(node2)
	node1.setRight(node3)
	node2.setLeft(node4)
	node4.setLeft(node6)
	node6.setLeft(node7)
	node4.setRight(node5)

	tree = Tree(node1)
	print "max length:", tree.getMaxLength()
	print "min length:", tree.getMinLength()

	copyTree = tree.copy()
	copyTree.root.right.value = 99
	print "Initial tree right value (want 3):", tree.root.right.value
	print "Node(1) == Node(1):", Node(1) == Node(1)
	print "Node(2) == Node(1):", Node(2) == Node(1)
	print "Node(1) == NodeNull():", Node(1) == NodeNull()
	print "NodeNull() == NodeNull():", NodeNull() == NodeNull()

